#include<iostream>
#include<stdio.h>
using namespace std;
int N = 9999;
#include<queue>
queue<int> q[200][200];
void Floyd(int matrix[][200],int n)
{
	int i = 0;
	for(i;i<n;i++)
	{
		int m = 0;
		for (m; m < n; m++)
		{
			int j = 0;
			for(j;j<n;j++)
			{
				if (matrix[m][j] > matrix[m][i] + matrix[i][j])
				{
					matrix[m][j] = matrix[m][i] + matrix[i][j];
					while(!q[m][j].empty())
					{
						q[m][j].pop();
					}
					int sz = q[m][i].size();
					queue<int> fq = q[m][i];
					while (sz--)
					{
						q[m][j].push(fq.front());
						fq.pop();
					}
					q[m][j].push(i);
					
				}
			}
		}
	}
}
int main()
{
	int n;
	cin >> n;
	int k = n;
	int matrix[200][200] = { 0 };
	int visit[200] = { 0 };
	int flag = 0;
	int i = 0;
	for (i; i < n; i++)
	{
		int j = 0;
		for (j; j < n; j++)
		{
			cin >> matrix[i][j];
			if (i == j)
				matrix[i][j] = 0;

			q[i][j].push(i);
		
		}
	}
	Floyd(matrix, n);
	
		int j = 0;
		for (j; j < n; j++)
		{
			int k = 0;
			for (k; k < n; k++)
			{
				printf("from %d to %d: dist = %d path:", j, k, matrix[j][k]);
				while (!q[j][k].empty())
				{
					cout << q[j][k].front() << ' ';
					q[j][k].pop();
				}
				if(k!=j)
				cout << k;
				cout << endl;
			}
		}
	
}